public class BubbleSort {

    private BubbleSort() {}

    public static <E extends Comparable<E>> void sort(E[] data) {
        if (data == null || data.length < 2) {
            return;
        }

        for (int i = 0; i + 1 < data.length; i++) {
            for (int j = 0; j + 1 < data.length - i; j++) {
                if (data[j].compareTo(data[j + 1]) > 0)
                    SortingHelper.swap(data, j, j + 1);
            }
        }
    }

    // 优化一: 交换计数, 每轮冒泡如果没有发生交换, 说明数组已经有序了, 可以直接结束排序
    public static <E extends Comparable<E>> void sort2(E[] data) {
        if (data == null || data.length < 2) {
            return;
        }

        for (int i = 0; i + 1 < data.length; i++) {
            boolean isSwapped = false;
            for (int j = 0; j + 1 < data.length - i; j++) {
                if (data[j].compareTo(data[j + 1]) > 0) {
                    SortingHelper.swap(data, j, j + 1);
                    isSwapped = true;
                }
            }
            if (!isSwapped)
                break;
        }
    }

    // 优化二: 最后一次交换位置计算
    public static <E extends Comparable<E>> void sort3(E[] data) {
        if (data == null || data.length < 2) {
            return;
        }

        for (int i = 0; i + 1 < data.length;) {
            int lastSwappedIndex = 0;
            for (int j = 0; j + 1 < data.length - i; j++) {
                if (data[j].compareTo(data[j + 1]) > 0) {
                    SortingHelper.swap(data, j, j + 1);
                    lastSwappedIndex = j + 1;
                }
            }
            i = data.length - lastSwappedIndex;
        }
    }

    // 理解i表示什么, 需要排序元素的个数,  运行过程中的i值表示已经有多少个元素已经排序了
    // [l, r)   r - l = 元素个数
    // TODO 换个方向实现冒泡排序算法, 从后向前冒泡, 完成优化版本
}
